import collections
class Solution(object):
    def knightProbability(self, n, k, row, column):
        """
        :type n: int
        :type k: int
        :type row: int
        :type column: int
        :rtype: float
        """
        c = 0
        p = 1
        now = {(row, column): 1}
        while c < k:
            t_count = 0
            c_count = 0
            next_set = collections.defaultdict(int)
            for x, y in now:
                base = now[(x, y)]
                for ux, uy in [(x - 2, y - 1), (x - 1, y - 2), (x - 2, y + 1), (x - 1, y + 2), (x + 1, y + 2),
                               (x + 2, y + 1), (x + 1, y - 2), (x + 2, y - 1)]:
                    t_count += base
                    if 0 <= ux < n and 0 <= uy < n:
                        c_count += base
                        next_set[(ux, uy)] += base
            now = next_set
            p *= (c_count / t_count)
            if p == 0:
                break
            c += 1
        return p

data = Solution()
n = 3
k = 2
row = 1
column = 1
print(data.knightProbability(n, k, row, column))